(1) Field of the Invention
The present invention relates to methods of active queue management in packet transmission systems, especially internet systems, telecommunications systems employing such methods and routers employing such methods.
(2) Description of the Related Art
The current Internet architecture offers one service only, namely, best-effort. The Internet community has recognized the importance of simplicity in the forwarding mechanisms, but has also recognized that this single service may not be enough to support the wide range of applications on the Internet. The Internet Engineering Task Force (IETF) is, therefore, designing architectural extensions to enable service differentiation on the Internet. The Differentiated Services (DiffServ) architecture, see:                Black D. et. al. (1998), An Architecture for Differentiated Services, IETF RFC 2475, December 1998;        Bernet Y. et. al. (1998), A Framework for Differentiated Services, IETF DRAFT, October 1998; and        Nichols K. et. al. (1998), Definition of the Differentiated Services Field (DS Field) in the IPv4 and 1Fv6 Headers, IETF RFC 2474, December 1998;includes mechanisms for differentiated forwarding.        
One proposed mechanism for DiffServ is to assign levels of drop precedence to IP packets. This mechanism is included in the Assured Forwarding (AF) per-hop behavior (PHB) group, see:                Hainanen J. et. al. (1998), Assured Forwarding PHB Group, IETF DRAFT, November 1998.        
AF can be used to offer differentiation among rate adaptive applications that respond to packet loss, e.g., applications using TCP. The traffic of each user is tagged as being in, or out of, their service profiles. Packets tagged as in profile are assigned a lower drop precedence than those tagged as out of profile. In addition, a packet within a users profile can be tagged with one, out of several levels, of drop precedence. For now, there are three levels of drop precedence for the AF PHB group.
Multiple levels of drop precedence can be created with an active queue management (AQM) mechanism applied to a FIFO queue. An advantageous property of FIFO queues is that packets are forwarded in the same order as they arrive. Thus, packet reordering, which can reduce the performance of a TCP connection, is avoided. Moreover, FIFO queues are suitable for high-speed links since they can be implemented efficiently.
Two known AQM mechanisms are RIO, see:
                Clark D. and Fang W. (1997), Explicit Allocation of Best Effort Delivery Service, 1997 URL http://www.diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.pdf,and WRED, see:        Technical Specification from Cisco (1998), Distributed Weighted Random Early Detection, 1998, URL: http://www.cisco.comlunivercd/cc/td/doc/productl/oftware/ios/111/cc111/wred.pdf;        
Normally, prioritized traffic entering a network is controlled to avoid overload. When such traffic is properly controlled, RIO and WRED are found to offer an absolute quantifiable differentiation. However, these mechanisms can cause starvation of less prioritized traffic if this control fails. That is, traffic tagged with anything but the highest prioritized level of drop precedence may suffer from starvation.
Failures in traffic control will occur due to inaccuracies in admission control and topology changes. For example, measurement based admission control may accidentally accept traffic causing a temporary overload until this condition is detected. Moreover, the control system, or the signalling protocol, may fail in adapting fast enough to changes in network routing topology. Traffic conditioners may, therefore, not be reconfigured before overload occurs. Thus, it is preferable if the AQM mechanism used can prevent starvation at any load.
RIO can be configured to prevent starvation, but a strict hierarchy among precedence levels cannot be guaranteed under periods of overload. That is, traffic tagged with the highest prioritized level of drop precedence may experience a larger drop rate than traffic tagged with a lesser prioritized level. Such a configuration of RIO is, therefore, not advisable. A queuing mechanism should not only prevent starvation, it should also preserve a strict hierarchy among precedence levels at any load.
A queuing mechanism creating multiple levels of drop precedence can be considered to be load-tolerant if it can meet the following two requirements at any load:                prevent starvation of low prioritized traffic—that is, low prioritized traffic must always get a useful share of the bandwidth available; and        preserve a strict hierarchy among precedence levels—that is, traffic using a certain precedence level must always experience less probability of loss than traffic using a less prioritized level of drop precedence.        
WRED can meet these requirements for load-tolerance when configured to offer a relative differentiation. A relative differentiation means, for example, that a TCP flow is given twice the throughput of another, less prioritized, TCP flow with the same RTT. That is, guarantees are made to one flow, only, relatively to another. An absolute differentiation, on the other hand, offers quantifiable bounds on throughput, loss and/or delay jitter. This kind of differentiation can give a TCP flow an absolute quantified throughput independent of the throughput other TCP flows will experience.
It can be assumed that absolute differentiable services are more desireable for many users than relative services, since they are more predictable. With an absolute service, the quality of a certain communication session is known in advance. This pre-knowledge is, for example, valuable when choosing the optimal level of redundancy coding. With a relative service, the level of coding has to be chosen based on heuristics, or real-time measurements.
Neither RIO, nor WRED, can meet the requirements for load-tolerance, stated above, while providing an absolute differentiation. The present invention, however, provides a new queuing mechanism, WRED with Thresholds (WRT). The benefit of the present invention, i.e. WRT, is that, without reconfiguration, it provides an absolute differentiation, if prioritized traffic is properly controlled, and a relative differentiation in other cases. Thus, WRT can be considered load-tolerant according to the definition stated above.
The load-tolerance of WRT can be examined by means of simulations. The simulations are focused on the qualitative behavior of WRT under different grades of overload, rather than its quantitative behavior at a specific load. Simulations comparing WRT with RIO and WRED show that WRT offers equal differentiation to these mechanisms. Thus, other simulation studies of RIO and WRED, providing quantitative results, are likely to be applicable to WRT.
For constructing end-to-end services, load-tolerance is advantageous for several reasons. First, traffic control does not need to be so accurate and/or a larger portion of prioritized traffic can be allowed in a network. Moreover, failure in controlling this prioritized traffic cannot cause any starvation.